package com.leetcode.algorithm.y22.m08.w5;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 946. 验证栈序列
 * 
 * https://leetcode.cn/problems/validate-stack-sequences/
 * 
 * @author jie.deng
 *
 */
class Question0946Solution01 {

	public boolean validateStackSequences(int[] pushed, int[] popped) {
		int len = pushed.length;
		int pushIdx = 0;
		int popIdx = 0;
		Deque<Integer> stack = new ArrayDeque<Integer>();
		while (pushIdx <= len && popIdx < len) {
			if (!stack.isEmpty() && stack.peek().intValue() == popped[popIdx]) {
				stack.pop();
				popIdx++;
			} else if (pushIdx < len) {
				if (pushed[pushIdx] == popped[popIdx]) {
					popIdx++;
					pushIdx++;
				} else {
					stack.push(pushed[pushIdx]);
					pushIdx++;
				}
			} else {
				return false;
			}
		}
		return true;
	}

}